/*************************************************************************
> File Name: peiShuSTheorem.cpp
> Author: icebear
> Mail: 3322366195@qq.com
> Created Time: 2024-01-11 21:42:39
> Description:
189 轮转数组
给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
************************************************************************/

// 思路：
// 找最大公约数，循环最大公约数次，每次在其中循环length/g次

#include <vector>
using namespace std;

class Solution
{
public:
    int gcd(int x, int y) // 求最大公约数
    {
        return y == 0 ? x : gcd(y, x % y);
    }
    void rotate(vector<int> &nums, int k)
    {
        int n = nums.size();
        k %= n;
        int g = gcd(k, n);
        int cnt = n / g;
        for (int i = 0; i <= g - 1; i++)
        {
            int j = i, cur = 0, pre = nums[j];
            while (cur < cnt)
            {
                int tmp = nums[(j + k) % n];
                nums[(j + k) % n] = pre;
                pre = tmp;
                j = (j + k) % n;
                cur++;
            }
        }
    }
};